Abstract: Quadratically constrained quadratic programs (QCQPs) form an important and fundamental class of optimization problems. In this problem, we are asked to minimize a (possibly nonconvex) quadratic function subject to a number of (possibly nonconvex) quadratic constraints. Such problems arise naturally in many areas of computer science, operations research and engineering—notably max-cut and max-clique can be cast naturally as QCQPs. Although QCQPs are NP-hard to solve in general, they admit a natural family of tractable convex relaxations. This talk will focus on the semidefinite program (SDP) relaxation for general QCQPs and revolve around the guiding question: “When does the computationally tractable SDP relaxation give us the correct solution to the underlying QCQP?” By analyzing the "geometry" of the SDP relaxation, we will give both sufficient conditions and necessary conditions for this behavior. In particular, we show that the SDP relaxation of “highly symmetric” QCQPs is exact.

This talk is presented in partial fulfillment of the speaking requirement and is based on joint work with Fatma Kilinc-Karzan and C.J. Argue.